package 算法;

import java.util.Random;

public class 快速排序 {
    public static void main(String[] args) {
        /*
        快速排序：
        1.第一次排序将0索引作为基准数，确定基准数在数组中的位置
          比基准数小的在左边，比基准数大的在右边
           思想：
           从起始索引（startIndex）或者终点索引（endIndex）开始进行查找
           startIndex++ 直到找到数组元素的值比基准数大，
           endIndex--直到找到数组元素的值比基准数小
           接下来，endIndex和startIndex交换元素
           重复以上步骤直至startIndex=endIndex结束排序

         */
        int[] arr = {5, 6, 20, 3, 94, 25, 30, 25, 1, 3, 9};
       /* int[] arr2 = new int[1000000];
        Random r = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt();
        }
        long start = System.currentTimeMillis();
        quickSort(arr,0,arr.length-1);
        long end = System.currentTimeMillis();
      */
        quickSort(arr, 0, arr.length - 1);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

    }

    /*
     * 参数一：要排序的数组
     * 参数二：要排序数组的起始索引
     * 参数三：要排序数组的结束索引
     * */
    public static void quickSort(int[] arr, int start, int end) {
//        定义两个索引位置
        int startIndex = start;
        int endIndex = end;
//            记录基准数
        if (startIndex > endIndex) {
            return;
//            递归结束
        }
        int baseNumber = arr[start];
//            利用循环找到交换的数字（前提条件：起始索引和终止索引不相等）
//        切记：一定要先移动end（是因为基准数在左边）
        while (startIndex != endIndex) {
//                 利用end从后向前找，找比基准书小的
            while (true) {
                if (endIndex <= startIndex || arr[endIndex] < baseNumber) {
                    break;
                }
                endIndex--;
            }
//                    利用start从前向后找，找比基准数大的
            while (true) {
                if (endIndex <= startIndex || arr[startIndex] > baseNumber) {
                    break;
                }

                startIndex++;
            }

//                    将end和start指向的元素进行交换
            int temp = arr[endIndex];
            arr[endIndex] = arr[startIndex];
            arr[startIndex] = temp;

        }
                /*
                当startIndex和endIndex指向同一个索引时结束循环
                表示找到基准数应该储的位置.
                接下来将startIndex和基准数进行交换
                 */
        int temp = arr[start];//arr[start]为基准数
        arr[start] = arr[startIndex];//将基准数和startIndex索引对应的元素进行交换
        arr[startIndex] = temp;

//        采用递归调用，重复执行
//        确定基准数左边的范围，重复quickSort方法
        quickSort(arr, start, startIndex - 1);
//        确定基准数右边的范围，重复quickSort方法
        quickSort(arr, startIndex + 1, end);
    }
}
